Allotment Routing Table – A Fast Free Multibit Trie Based Routing Table,” http://www.hariguchi.org/art/art.pdf

After introduction of the Classless Inter-Domain Routing, several high speed longest prefix matching route lookup algorithms were proposed. Among them, it is known that multibit trie based routing tables, particularly the techniques called Controlled Prefix Expansion (CPE) and Smart Multi-Array Routing Table (SMART) have a low and deterministic search cost of modestly higher memory con-sumption. Their search cost is typically 3 to 4 routing table memory accesses for IPv4. However, no one can use them without licensing since they are patented or patent pend-ing. This paper presents a new freely reusable multibit trie based routing table called Allotment Routing Table (ART) which is as fast as both the CPE and SMART. The IPv4 per-formance of one ART configuration is 10M lookups/sec for search, 800K routes/sec for insertion, and 2.04M routes/sec for deletion on a Pentium III 1GHz PC. This is 16 times in search, 50 % in insertion, 4 times in deletion as fast as the BSD radix with 3 times more memory consumption; an-other ART configuration has the performance of more than 8 times in search, 2 times in inseartion, 50 % in deletion as fast as the BSD radix with less memory consumption. This paper also describes the path compression technique. The algorithms of ART are in the public domain. The au-thor’s ART implementations and an ART implementation in the KAME IPv6 stack for the BSD kernel are also freely reusable.